package com.heng.test;

import java.lang.String;
import java.util.ArrayList;
import java.util.Arrays;


public class Tree {
    static ArrayList[] e = new ArrayList[13];
    static int[] fa = new int[13];//存
    static int[] dep = new int[13];
    static int[] son = new int[13];
    static int[] sz = new int[13];
    static int[] top = new int[13];

    static void dfs1(int u, int father) {
        fa[u] = father;
        dep[u] = dep[father] + 1;
        sz[u] = 1;
        for (int i = 0 ;i < e[u].size();i++) {
            Integer v = (Integer) e[u].get(i);

            if (v == father) continue;
            dfs1(v,u);
            sz[u]+=sz[v];
            if(sz[son[u]] < sz[v]) son[u] = v;
        }
    }

    static void dfs2(int u, int t) {
        top[u] = t;
        if (son[u] == 0) return;
        dfs2(son[u], t);
        for (int i = 0; i < e[u].size(); i++) {
            int v = (int) e[u].get(i);
            if (v == fa[u] || v == son[u]) continue;
            dfs2(v,v);
        }
    }

    static int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) {
                //swap(u,v);
                int temp = u;
                u = v;
                v = temp;
            }
            u = fa[top[u]];
        }
        return dep[u] < dep[v]?u:v;
    }

    public static void main(String[] args) {
        for (int i = 0; i < e.length; i++) {
            e[i] = new ArrayList<Integer>();
        }

        e[1].add(2);
        e[1].add(3);
        e[1].add(4);

        e[2].add(5);
        e[2].add(6);

        e[3].add(7);
        e[4].add(8);
        e[4].add(9);

        e[6].add(10);

        e[8].add(11);
        e[8].add(12);

        dfs1(1,0);
        dfs2(1,1);

        System.out.println(Arrays.toString(son));
        System.out.println(Arrays.toString(fa));
        System.out.println(Arrays.toString(sz));
        System.out.println(Arrays.toString(top));

        int lca = lca(10, 11);
        System.out.println(lca);
    }


}
